package cn.mayday.algorithms.year2021.month1.E堆和TopN专题;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @description: 剑指Offer40. 最小的k个数
 * @author: mayday
 * @date: 2020/9/12 17:30
 * @version: 1.0
 */
public class Arrow40MinK {

    public static void main(String[] args) {

    }


    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr.length == 0 || k == 0) {
            return new int[0];
        }

        // 使用一个最大堆（大顶堆）. 这种找最小的K个数，对应建立大顶堆，相反找最大的K个数，对应建立小顶堆
        // Java 的 PriorityQueue 默认是小顶堆，添加 comparator 参数使其变成最大堆
        Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

        for (int temp : arr) {
            // 大顶堆未达到K值时，无需比较，直接入堆
            if (heap.size() < k) {
                heap.offer(temp);
            } else {
                // 所谓的大顶堆，即堆顶为当前最大值，如果待比较数值比最大的小，则先最大的出堆，并且待比较数值入堆（并且调整新的最大数值到堆顶）
                if (temp < heap.peek()) {
                    heap.poll();
                    heap.offer(temp);
                }
            }
        }

        // 输出
        int[] result = new int[heap.size()];
        int count = 0;
        for (int temp : heap) {
            result[count++] = temp;
        }
        return result;
    }
}
